# import the necessary packages
from scipy.spatial import distance as dist
from collections import OrderedDict
import numpy as np

class CentroidTracker():
	def __init__(self, maxDisappeared=50):
		# 初始化新出现的目标的id 和两个字典。它们分别用于跟踪给定对象ID到其质心的映射
		# 以及它被标记为“消失”的对象的连续帧的数量
		self.nextObjectID = 0 # id
		self.objects = OrderedDict() # 有序字典, 存储目标，格式为{(id, centroid), ...}
		self.disappeared = OrderedDict() # 有序字典，存储已经消失的目标的次数，格式{(id, 丢失次数)， ... }

        # 最大的消失次数，如果(被追踪的)目标的消失次数大于此值, 则可以认为该目标消失.
		self.maxDisappeared = maxDisappeared

	def register(self, centroid):
		# 当注册一个对象时, 使用一个可用的id注册质心
		self.objects[self.nextObjectID] = centroid # 登记跟踪对象的id 和 centroid
		self.disappeared[self.nextObjectID] = 0	# 对象(id)丢失次数为 0
		self.nextObjectID += 1

	def deregister(self, objectID):
		# 要取消对象id, 需要从各自的字典中删除对象
		del self.objects[objectID]
		del self.disappeared[objectID]

	def update(self, rects):
		"""
		参数: rects: 矩形标记框列表, 格式: [(x1, y1, x2, y2), ...]
		"""
		# 如果矩形标记框列表为空(说明此帧没有识别到物体)，则增加追踪的目标的消失次数;
		if len(rects) == 0:
            # 循环已跟踪的对象，增加已跟踪对象的消失次数
			for objectID in list(self.disappeared.keys()):
				self.disappeared[objectID] += 1

                # 如果某个对象消失次数已经达到了“丢失”的最大值, 我们就删除该对象
				if self.disappeared[objectID] > self.maxDisappeared:
					self.deregister(objectID)

			# 返回跟踪对象字典
			return self.objects

        # 初始化当前帧质心数组, inputCentroids格式为[n, 2]
		inputCentroids = np.zeros((len(rects), 2), dtype="int")

        # 循环访问矩形边框列表
		for (i, (startX, startY, endX, endY)) in enumerate(rects):
            # 使用边界框坐标计算质心
			cX = int((startX + endX) / 2.0)
			cY = int((startY + endY) / 2.0)
			inputCentroids[i] = (cX, cY)

        # 如果我们当前没有任何跟踪的对象，则注册全部的质心
		if len(self.objects) == 0:
			for i in range(0, len(inputCentroids)):
				self.register(inputCentroids[i])

        # 否则，我们需要尝试匹配已有的对象的质心
		else:
            # 获取旧跟踪的对象id和质心坐标
			objectIDs = list(self.objects.keys()) # 旧质心id列表
			objectCentroids = list(self.objects.values()) # 旧质心坐标列表

            # 分别计算旧质心与新质心之间的欧式距离， D 的格式如下：
            # D = [[d11, d12, d13], 旧质心id1到新质心集合{id1, id2, id3}的欧式距离
            #	   [d21, d22, d23], 旧质心id2到新质心集合{id1, id2, id3}的欧式距离
            #      【d31, d32, d33]] 旧质心id3到新质心集合{id1, id2, id3}的欧式距离
			D = dist.cdist(np.array(objectCentroids), inputCentroids)

            # 为了执行这种匹配，我们必须
            #（1）找到每行中的最小值，然后
            #（2）根据最小值对行索引进行排序，以便值最小的行位于索引列表的 “前端” 处
            # 例子 rows = [2, 0, 1], 表示D中第2行存在最小的值, D中第0行存在第2小的值, ...
			rows = D.min(axis=1).argsort() # rows 是行索引

            # 输出指定行最小值的下标，按照[rows]
            # 例子： cols = [3, 0, 2], 表示每一行中最小值下标为[3, 0, 2]
			cols = D.argmin(axis=1)[rows]

            # 存储已经检查过的行和列
			usedRows = set()
			usedCols = set()

			# 循环取出每行最小值的下标
			for (row, col) in zip(rows, cols):
				# 忽略已经检查的行和列
				if row in usedRows or col in usedCols:
					continue

				# 更新旧目标的质心坐标
				objectID = objectIDs[row]
				self.objects[objectID] = inputCentroids[col]
				self.disappeared[objectID] = 0

				# indicate that we have examined each of the row and
				# column indexes, respectively
				# 记录已经检查过的行和列
				usedRows.add(row)
				usedCols.add(col)

			# 计算还没有检查的行索引和列索引
			unusedRows = set(range(0, D.shape[0])).difference(usedRows)
			unusedCols = set(range(0, D.shape[1])).difference(usedCols)

			# 如果 D.shape[0] >= D.shape[1], 旧质心数量多于新质心数量，
			# 多出的旧质心并没有匹配项目，我们要新增旧质心的消失数量
			if D.shape[0] >= D.shape[1]:
				# 循环遍历多余的旧质心
				for row in unusedRows:
					# 对多余的旧质心增加消失次数
					objectID = objectIDs[row]
					self.disappeared[objectID] += 1

					# 如果消失次数大于最大消失次数，则删除该质心
					if self.disappeared[objectID] > self.maxDisappeared:
						self.deregister(objectID)

			# 如果 D.shape[0] < D.shape[1], 则新质心数量多于旧质心数量, 
			# 我们要登记新增的质心
			else:
				for col in unusedCols:
					self.register(inputCentroids[col])

		# 返回跟踪的对象
		return self.objects